//给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中
//sequences[i] 是 nums 的子序列。 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列
//sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
//
//
// 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
// 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超
//序列，但不是最短的。
//
//
// 如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。 子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素
//，而不改变其余元素的顺序的序列。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
//输出：false
//解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
//序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
//序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
//因为 nums 不是唯一最短的超序列，所以返回false。
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3], sequences = [[1,2]]
//输出：false
//解释：最短可能的超序列为 [1,2]。
//序列 [1,2] 是它的子序列：[1,2]。
//因为 nums 不是最短的超序列，所以返回false。
//
//
// 示例 3：
//
//
//输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
//输出：true
//解释：最短可能的超序列为[1,2,3]。
//序列 [1,2] 是它的一个子序列：[1,2,3]。
//序列 [1,3] 是它的一个子序列：[1,2,3]。
//序列 [2,3] 是它的一个子序列：[1,2,3]。
//因为 nums 是唯一最短的超序列，所以返回true。
//
//
//
// 提示：
//
//
// n == nums.length
// 1 <= n <= 10⁴
// nums 是 [1, n] 范围内所有整数的排列
// 1 <= sequences.length <= 10⁴
// 1 <= sequences[i].length <= 10⁴
// 1 <= sum(sequences[i].length) <= 10⁵
// 1 <= sequences[i][j] <= n
// sequences 的所有数组都是 唯一 的
// sequences[i] 是 nums 的一个子序列
//
//
//
//
// 注意：本题与主站 444 题相同：https://leetcode-cn.com/problems/sequence-reconstruction/
//
// Related Topics 图 拓扑排序 数组 👍 135 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/*
? 初始时遍历sequences中的所有元素，对于sequences中的[a, b, c]，构建一条a→b的边和一条b→c的边，并把b和c的入度+1
? 遍历所有节点，将入度为0的节点入队。不断从队列中取出节点，去掉从这个节点开始的所有的边，并把去掉的边所指向的节点的入度-1。（假如从节点a出发有两条边a→b和a→c，那么b和c的入度-1）
? 直到队列为空
? 注意：
? 整个排序过程中，队列中最多有1个节点。（那是因为如果同时有多个入度为0的节点，就无法判断这些节点之间的相对顺序）
? 排序结束后，所有节点的入度必须全部为0
? 如果满足上述两个条件中的一个，就返回true
 */
function sequenceReconstruction(nums: number[], sequences: number[][]): boolean {
    let len: number = nums.length
    let map: number[][] = new Array(len + 1)  //? map[i]表示i指向的节点的数组
    for (let i = 0; i < map.length; i++) map[i] = new Array()
    let degree: number[] = new Array(len + 1).fill(0)
    degree[0] = -1  //? degree[i]表示i的度数，nums是从1开始的，所以0没用

    //? 存入map
    sequences.forEach(it => {
        for (let i = 1; i < it.length; i++) {
            //? 存放i=0处的连通点
            map[it[i - 1]].push(it[i])
            //? i的入度+1
            degree[it[i]]++
        }
    })

    //? 拓扑排序
    let que: number[] = []
    //? 入度为0的数字进入队列
    degree.forEach((it, idx) => {if (it === 0) que.push(idx)})

    while (que.length) {
        //? 如果有多个入度为0的点，那么就是无法推测唯一最短序列
        if (que.length > 1) return false
        let idx: number = que.shift()
        let sons: number[] = map[idx]
        sons.forEach(it => {
            degree[it]-- //? 所有的儿子，入度-1
            if (!degree[it]) que.push(it)  //? 再次查找入度为0的节点
        })
    }

    return !degree.some((val) => val > 0)   //? 如果存在入度大于0的，证明有问题 到最后应该不剩有入度为非0的
}


//leetcode submit region end(Prohibit modification and deletion)
